<!DOCTYPE HTML>
<html lang="en" class="sidebar-visible no-js light">
    <head>
        <!-- Book generated using mdBook -->
        <meta charset="UTF-8">
        <title>Mapreduce - 读论文</title>


        <!-- Custom HTML head -->
        
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff" />

        <link rel="icon" href="favicon.svg">
        <link rel="shortcut icon" href="favicon.png">
        <link rel="stylesheet" href="css/variables.css">
        <link rel="stylesheet" href="css/general.css">
        <link rel="stylesheet" href="css/chrome.css">
        <link rel="stylesheet" href="css/print.css" media="print">

        <!-- Fonts -->
        <link rel="stylesheet" href="FontAwesome/css/font-awesome.css">
        <link rel="stylesheet" href="fonts/fonts.css">

        <!-- Highlight.js Stylesheets -->
        <link rel="stylesheet" href="highlight.css">
        <link rel="stylesheet" href="tomorrow-night.css">
        <link rel="stylesheet" href="ayu-highlight.css">

        <!-- Custom theme stylesheets -->

        <!-- MathJax -->
        <script async type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
    </head>
    <body>
        <!-- Provide site root to javascript -->
        <script type="text/javascript">
            var path_to_root = "";
            var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
        </script>

        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script type="text/javascript">
            try {
                var theme = localStorage.getItem('mdbook-theme');
                var sidebar = localStorage.getItem('mdbook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script type="text/javascript">
            var theme;
            try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
            if (theme === null || theme === undefined) { theme = default_theme; }
            var html = document.querySelector('html');
            html.classList.remove('no-js')
            html.classList.remove('light')
            html.classList.add(theme);
            html.classList.add('js');
        </script>

        <!-- Hide / unhide sidebar before it is displayed -->
        <script type="text/javascript">
            var html = document.querySelector('html');
            var sidebar = 'hidden';
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            }
            html.classList.remove('sidebar-visible');
            html.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <div class="sidebar-scrollbox">
                <ol class="chapter"><li class="chapter-item expanded affix "><a href="chapter_1.html">读论文活动</a></li><li class="chapter-item expanded affix "><li class="part-title">6.824 分布式系统</li><li class="chapter-item expanded "><a href="Mapreduce.html" class="active"><strong aria-hidden="true">1.</strong> Mapreduce</a></li><li class="chapter-item expanded "><a href="GFS.html"><strong aria-hidden="true">2.</strong> GFS</a></li><li class="chapter-item expanded "><a href="VM-FT.html"><strong aria-hidden="true">3.</strong> VM-FT</a></li><li class="chapter-item expanded "><a href="Raft.html"><strong aria-hidden="true">4.</strong> Raft</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="Raft0.html"><strong aria-hidden="true">4.1.</strong> 感性认识Raft</a></li><li class="chapter-item expanded "><a href="Raft1.html"><strong aria-hidden="true">4.2.</strong> 什么是Raft？</a></li><li class="chapter-item expanded "><a href="Raft2.html"><strong aria-hidden="true">4.3.</strong> 复制状态机（Replicated State Machine）</a></li><li class="chapter-item expanded "><a href="Raft3.html"><strong aria-hidden="true">4.4.</strong> What's wrong with Paxos?</a></li><li class="chapter-item expanded "><a href="Raft4.html"><strong aria-hidden="true">4.5.</strong> 向可理解性进军</a></li><li class="chapter-item expanded "><a href="Raft5.html"><strong aria-hidden="true">4.6.</strong> Raft共识算法（零）</a></li><li class="chapter-item expanded "><a href="Raft6.html"><strong aria-hidden="true">4.7.</strong> Raft共识算法（一）——基础概念</a></li><li class="chapter-item expanded "><a href="Raft7.html"><strong aria-hidden="true">4.8.</strong> Raft共识算法（二）——选举leader</a></li><li class="chapter-item expanded "><a href="Raft8.html"><strong aria-hidden="true">4.9.</strong> Raft共识算法（三）——日志备份（log replication）</a></li><li class="chapter-item expanded "><a href="Raft9.html"><strong aria-hidden="true">4.10.</strong> Raft共识算法（四）——安全性和选举限制</a></li><li class="chapter-item expanded "><a href="Raft10.html"><strong aria-hidden="true">4.11.</strong> Raft共识算法（五）——如何提交之前term里的entry</a></li><li class="chapter-item expanded "><a href="Raft11.html"><strong aria-hidden="true">4.12.</strong> Raft共识算法（六）——安全性定理</a></li><li class="chapter-item expanded "><a href="Raft12.html"><strong aria-hidden="true">4.13.</strong> Raft共识算法（七）——如果follower/candidate宕机了</a></li><li class="chapter-item expanded "><a href="Raft13.html"><strong aria-hidden="true">4.14.</strong> Raft共识算法（八）——时间与可用性</a></li><li class="chapter-item expanded "><a href="Raft14.html"><strong aria-hidden="true">4.15.</strong> 成员变更</a></li><li class="chapter-item expanded "><a href="Raft15.html"><strong aria-hidden="true">4.16.</strong> 日志压缩</a></li><li class="chapter-item expanded "><a href="Raft16.html"><strong aria-hidden="true">4.17.</strong> 与Client的交互</a></li><li class="chapter-item expanded "><a href="Raft17.html"><strong aria-hidden="true">4.18.</strong> 实验时遇到的bug</a></li><li class="chapter-item expanded "><a href="Raft18.html"><strong aria-hidden="true">4.19.</strong> 总结</a></li></ol></li><li class="chapter-item expanded "><a href="Zookeeper.html"><strong aria-hidden="true">5.</strong> Zookeeper</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="linearizability1.html"><strong aria-hidden="true">5.1.</strong> 线性一致性（一）——基础概念</a></li><li class="chapter-item expanded "><a href="linearizability2.html"><strong aria-hidden="true">5.2.</strong> 线性一致性（二）——细究linearizability</a></li><li class="chapter-item expanded "><a href="zk_intro.html"><strong aria-hidden="true">5.3.</strong> 引言</a></li><li class="chapter-item expanded "><a href="zk_service.html"><strong aria-hidden="true">5.4.</strong> Zookeeper Service</a></li><li class="chapter-item expanded "><a href="zk_api.html"><strong aria-hidden="true">5.5.</strong> Zookeeper API</a></li><li class="chapter-item expanded "><a href="zk_prop.html"><strong aria-hidden="true">5.6.</strong> Zookeeper的性质</a></li><li class="chapter-item expanded "><a href="zk_ex.html"><strong aria-hidden="true">5.7.</strong> 基于Zookeeper实现锁</a></li></ol></li><li class="chapter-item expanded "><a href="CRAQ.html"><strong aria-hidden="true">6.</strong> CRAQ</a></li><li class="chapter-item expanded "><a href="lamport_clock.html"><strong aria-hidden="true">7.</strong> Time, Clocks, and the Ordering of Events in a Distributed System</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="lamport_clock1.html"><strong aria-hidden="true">7.1.</strong> 引言</a></li><li class="chapter-item expanded "><a href="lamport_clock_partial_order.html"><strong aria-hidden="true">7.2.</strong> 偏序关系</a></li><li class="chapter-item expanded "><a href="lamport_logic_clock.html"><strong aria-hidden="true">7.3.</strong> 逻辑时钟</a></li><li class="chapter-item expanded "><a href="lamport_total_order.html"><strong aria-hidden="true">7.4.</strong> 全序关系</a></li><li class="chapter-item expanded "><a href="lamport_clock_ana_behave.html"><strong aria-hidden="true">7.5.</strong> 异常事件</a></li><li class="chapter-item expanded "><a href="lamport_p_clock.html"><strong aria-hidden="true">7.6.</strong> 物理时钟</a></li><li class="chapter-item expanded "><a href="lamport_end.html"><strong aria-hidden="true">7.7.</strong> 结论</a></li></ol></li><li class="chapter-item expanded "><li class="part-title">6.828 操作系统</li><li class="chapter-item expanded "><a href="828intro.html"><strong aria-hidden="true">8.</strong> Killer of Microseconds</a></li><li class="chapter-item expanded "><a href="cloudlab.html"><strong aria-hidden="true">9.</strong> CloudLab</a></li><li class="chapter-item expanded "><a href="dpdk.html"><strong aria-hidden="true">10.</strong> DPDK</a></li><li class="chapter-item expanded "><a href="spdk.html"><strong aria-hidden="true">11.</strong> SPDK</a></li><li class="chapter-item expanded "><a href="Shenango.html"><strong aria-hidden="true">12.</strong> Shenango</a></li><li class="chapter-item expanded "><a href="TritonSort.html"><strong aria-hidden="true">13.</strong> TritonSort</a></li><li class="chapter-item expanded "><a href="Profiling.html"><strong aria-hidden="true">14.</strong> Profiling a warehouse-scale computer</a></li><li class="chapter-item expanded affix "><li class="part-title">6.828 - Network</li><li class="chapter-item expanded affix "><li class="part-title">CS244 - Advanced Topics in Networking</li><li class="chapter-item expanded "><a href="DARPA_NET.html"><strong aria-hidden="true">15.</strong> The Design Philosophy of The DARPA Internet Protocols</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="DARPA_NET2.html"><strong aria-hidden="true">15.1.</strong> Second Level Goals</a></li><li class="chapter-item expanded "><a href="DARPA_NET3.html"><strong aria-hidden="true">15.2.</strong> Types of Service</a></li><li class="chapter-item expanded "><a href="DARPA_NET4.html"><strong aria-hidden="true">15.3.</strong> Varieties of Networks</a></li><li class="chapter-item expanded "><a href="DARPA_NET5.html"><strong aria-hidden="true">15.4.</strong> Architecture and Implementation</a></li><li class="chapter-item expanded "><a href="DARPA_NET6.html"><strong aria-hidden="true">15.5.</strong> Datagrams</a></li></ol></li><li class="chapter-item expanded "><li class="part-title">最后</li><li class="chapter-item expanded "><a href="end.html"><strong aria-hidden="true">16.</strong> 最后</a></li></ol>
            </div>
            <div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
        </nav>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                                <div id="menu-bar-hover-placeholder"></div>
                <div id="menu-bar" class="menu-bar sticky bordered">
                    <div class="left-buttons">
                        <button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                            <i class="fa fa-bars"></i>
                        </button>
                        <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                            <i class="fa fa-paint-brush"></i>
                        </button>
                        <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                            <li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                        </ul>
                        <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
                            <i class="fa fa-search"></i>
                        </button>
                    </div>

                    <h1 class="menu-title">读论文</h1>

                    <div class="right-buttons">
                        <a href="print.html" title="Print this book" aria-label="Print this book">
                            <i id="print-button" class="fa fa-print"></i>
                        </a>

                    </div>
                </div>

                <div id="search-wrapper" class="hidden">
                    <form id="searchbar-outer" class="searchbar-outer">
                        <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                    </form>
                    <div id="searchresults-outer" class="searchresults-outer hidden">
                        <div id="searchresults-header" class="searchresults-header"></div>
                        <ul id="searchresults">
                        </ul>
                    </div>
                </div>

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script type="text/javascript">
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <main>
                        <h1 id="mapreduce"><a class="header" href="#mapreduce">Mapreduce</a></h1>
<p>分布式计算入门必看的论文：<a href="./assets/mapreduce.pdf">mapreduce.pdf</a></p>
<p>强烈大家建议去做6.824的lab1。</p>
<blockquote>
<p>我反对！我常跟行家讲，周董是我的偶像！
工程抢过来不必自己做，十亿先拿掉五亿，接下来发包，两转三转，四五六七八转，
你不赚钱想办法偷工减料，再下来跟营建署勾结，追加三五亿预算，
这个工程下来，我看你起码拿掉七亿，你分给我们这么一点点的钱，你还有良心啊?</p>
<p align="right">——电影《黑金》</p>
</blockquote>
<h2 id="mapreduce-simplified-data-processing-on-large-clusters"><a class="header" href="#mapreduce-simplified-data-processing-on-large-clusters">MapReduce: Simplified Data Processing on Large Clusters</a></h2>
<h2 id="摘要"><a class="header" href="#摘要">摘要</a></h2>
<blockquote>
<p>MapReduce is a programming model and an associated implementation for processing and generating large data sets.<br />
Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs,
and a reduce function that merges all intermediate values associated with the same intermediate key.<br />
Many real world tasks are expressible in this model, as shown in the paper.</p>
<p>Programs written in this functional style are automatically parallelized and executed on a large cluster of commodity machines.<br />
The run-time system takes care of the details of partitioning the input data,
scheduling the pro- gram’s execution across a set of machines,
handling machine failures, and managing the required inter-machine communication.<br />
This allows programmers without any experience with parallel and distributed systems to easily utilize the resources of a large distributed system.</p>
<p>Our implementation of MapReduce runs on a large cluster of commodity machines and is highly scalable:
a typical MapReduce computation processes many terabytes of data on thousands of machines.<br />
Programmers find the system easy to use: hundreds of MapReduce programs have been implemented and upwards of one thousand MapReduce jobs are executed on Google’s clusters every day.</p>
</blockquote>
<h2 id="结论"><a class="header" href="#结论">结论</a></h2>
<blockquote>
<p>The MapReduce programming model has been successfully used at Google for many different purposes.<br />
We attribute this success to several reasons.<br />
First, the model is easy to use, even for programmers without experience with parallel and distributed systems, since it hides the details of parallelization, fault-tolerance, locality optimization, and load balancing.<br />
Second, a large variety of problems are easily expressible as MapReduce com- putations.<br />
For example, MapReduce is used for the generation of data for Google’s production web search service, for sorting, for data mining, for machine learning, and many other systems.<br />
Third, we have developed an implementation of MapReduce that scales to large clusters of machines comprising thousands of machines.<br />
The implementation makes efficient use of these machine re- sources and therefore is suitable for use on many of the large computational problems encountered at Google.</p>
</blockquote>
<h2 id="分布式系统概念"><a class="header" href="#分布式系统概念">分布式系统概念</a></h2>
<p>定义：</p>
<ul>
<li>若干计算机组成的集群，通过网络通信，共同完成一系列具有耦合性（coherent）的任务。</li>
</ul>
<p>目的：</p>
<ul>
<li>提高吞吐量（大型存储系统）</li>
<li>容错/容灾（保持服务高可用/两地三中心）</li>
<li>使计算过程物理独立（服务下沉）</li>
<li>使计算节点具有一定的隔离性，从而保证安全（区块链）</li>
</ul>
<p>复杂性：</p>
<ul>
<li>系统间不同部分的交互</li>
<li>局部错误（机器、磁盘故障等）</li>
<li>性能瓶颈（性能不一定正比于机器数量）</li>
</ul>
<p>学习分布式的意义：</p>
<ul>
<li>计算机科学的掌上明珠</li>
<li>Interesting unsolved questions</li>
<li>提高动手能力</li>
<li>提升系统设计的思想和理念</li>
</ul>
<h2 id="什么是mapreduce"><a class="header" href="#什么是mapreduce">什么是mapreduce？</a></h2>
<p>谷歌推出的，可水平扩展的，分布式计算框架</p>
<h2 id="背景"><a class="header" href="#背景">背景</a></h2>
<p>早在2003年之前，谷歌作为一家搜索起家的公司，需要解决的问题有：统计单词在文本中出现的数量、建立单词在文档中出现的索引、统计url被点击的数量、排序。</p>
<p>每一个问题都很直观简单，但是当数据量增大至TB乃至PB量级的时候，没有一台单机可以进行这样简单的计算。</p>
<p>最开始，谷歌招募了一些懂分布式系统设计的程序员，针对具体任务去写分布式的业务代码。但是谷歌作为一家需要控制成本和盈利的公司，领导层绝不会希望每一个程序员都是需要懂分布式的。</p>
<p>于是，很自然的，谷歌提出设计一个系统，系统的设计者负责提供通用的分布式计算框架，该框架最重要的特性是支持水平扩展（scale）；而系统的使用者，只需要很少的心智负担，即可使用这个框架来解决他们的大数据量的计算问题。</p>
<h2 id="以word_count为例讲解什么是map和reduce"><a class="header" href="#以word_count为例讲解什么是map和reduce">以word_count为例，讲解什么是map和reduce</a></h2>
<p>我们先来假设一个问题，通过这个问题来引出什么是map和reduce。假如你是一个大学的图书馆管理员，手底下有一群勤工俭学的大学生，现在校长想统计整个图书馆所有的图书中每个单词出现的次数。你应该怎么给手底下的学生分配任务呢？</p>
<p>在这个问题里，你是这个分布式系统的master，勤工俭学的学生是worker，而校长则是client。</p>
<hr />
<p>首先很自然地想到，你可以先把图书平均分给每一个学生，然后让他们进行每一本书的单词统计。这样的话，比如学生A拿到了《他改变了中国》《He changed China》两本书，然后给出的统计结果是这样的：</p>
<pre><code>当特首 1
吼啊 1
当然啦 1
naive 1
exciting 1
</code></pre>
<p>学生B拿到了《红楼梦》《The Red Building Dream》两本书，然后B给出的结果是</p>
<pre><code>吼啊 1
当然啦 1
naive 1
exciting 1
</code></pre>
<hr />
<p>那么然后呢？A和B的结果里包含了相同的key，我们如何对这些相同的key进行一个汇总？（在这里，汇总的语义是什么？）</p>
<p>不难想到，我们只要让A和B的统计结果中，具有相同的key被统一地进一步处理就好啦。比方说我们现在还有两个同学C和D，我们可以简单的让C处理中文的统计，D处理英文的统计。那么C的处理结果就是</p>
<pre><code>当特首 1
吼啊 2
当然啦 2
</code></pre>
<p>D的处理结果就是</p>
<pre><code>naive 2
exciting 2
</code></pre>
<p>于是我们只要把C和D的统计结果进行合并就好啦。</p>
<hr />
<p>P.S: 作为程序员，很自然的可以想到一种key的分配方式：</p>
<p>假设我们有n个同学（编号为0, 1, 2, ..., n-1）被分配来做汇总工作，那么对于每个key，对它做汇总工作的同学的编号应为：</p>
<p>$$ i=hash(key) % n $$</p>
<hr />
<p>来整理和更细化一下刚才的过程吧，作为master，我们有A、B、C、D四个worker。</p>
<p>首先在第一阶段，我们将要处理的文件进行了摊派(map)，A和B拿到了书名和书中的内容，对应到计算机中，即filename和content。</p>
<p>A和B处理完成后，A知道他需要把中文的key留给C做汇总，英文的key留给D做汇总。于是A输出的文件为&quot;map-A-C&quot;和&quot;map-A-D&quot;，同理B的输出文件为&quot;map-B-C&quot;和“map-B-D”。</p>
<p>在第二阶段，我们需要将第一阶段得到的中间结果进行汇总(reduce)，现在有C和D，C知道自己要处理的文件为&quot;map-A-C&quot;和&quot;map-B-C&quot;，D知道自己要处理的文件为&quot;map-A-D&quot;和&quot;map-B-D&quot;。</p>
<p>最终C和D的输出文件为&quot;reduce-C&quot;和&quot;reduce-D&quot;，然后我们将这两个文件进行合并就是最后的结果。</p>
<p>于是，Mapreduce的抽象表达也就呼之欲出了⬇️</p>
<h2 id="mapreduce的抽象表达"><a class="header" href="#mapreduce的抽象表达">Mapreduce的抽象表达</a></h2>
<p>$$ map(k1, v1) \rightarrow     list(k2, v2') $$
$$ reduce(k2, list(v2'))  \rightarrow  v2 $$</p>
<p><code>k1</code>一般是文件名，<code>v1</code>是文件里的内容，map的任务是将<code>k1</code>和<code>v1</code>转化成一堆键值对<code>k2, v2'</code>。<br />
<code>k2</code>和<code>v2'</code>是中间结果，reduce的任务就是对具有相同键的中间结果做处理，得到最终结果<code>v2</code>。</p>
<h2 id="show-me-code"><a class="header" href="#show-me-code">Show me code</a></h2>
<p>还是懵懵懂懂的吗？要不看看代码？</p>
<h3 id="先来看单点按顺序执行的程序"><a class="header" href="#先来看单点按顺序执行的程序">先来看单点按顺序执行的程序</a></h3>
<pre><code class="language-bash">
$ git clone git://g.csail.mit.edu/6.824-golabs-2021 6.824
$ cd 6.824

</code></pre>
<p>在<code>main</code>目录下的<code>mrsequential.go</code>中有：</p>
<pre><code class="language-go">package main

//
// simple sequential MapReduce.
//
// go run mrsequential.go wc.so pg*.txt
//

import &quot;fmt&quot;
import &quot;../mr&quot;
import &quot;plugin&quot;
import &quot;os&quot;
import &quot;log&quot;
import &quot;io/ioutil&quot;
import &quot;sort&quot;

// for sorting by key.
type ByKey []mr.KeyValue

// for sorting by key.
func (a ByKey) Len() int           { return len(a) }
func (a ByKey) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByKey) Less(i, j int) bool { return a[i].Key &lt; a[j].Key }

func main() {
   if len(os.Args) &lt; 3 {
      fmt.Fprintf(os.Stderr, &quot;Usage: mrsequential xxx.so inputfiles...\n&quot;)
      os.Exit(1)
   }

   mapf, reducef := loadPlugin(os.Args[1])

   //
   // read each input file,
   // pass it to Map,
   // accumulate the intermediate Map output.
   //
   intermediate := []mr.KeyValue{}
   for _, filename := range os.Args[2:] {
      file, err := os.Open(filename)
      if err != nil {
         log.Fatalf(&quot;cannot open %v&quot;, filename)
      }
      content, err := ioutil.ReadAll(file)
      if err != nil {
         log.Fatalf(&quot;cannot read %v&quot;, filename)
      }
      file.Close()
      kva := mapf(filename, string(content))
      intermediate = append(intermediate, kva...)
   }

   //
   // a big difference from real MapReduce is that all the
   // intermediate data is in one place, intermediate[],
   // rather than being partitioned into NxM buckets.
   //

   sort.Sort(ByKey(intermediate))

   oname := &quot;mr-out-0&quot;
   ofile, _ := os.Create(oname)

   //
   // call Reduce on each distinct key in intermediate[],
   // and print the result to mr-out-0.
   //
   i := 0
   for i &lt; len(intermediate) {
      j := i + 1
      for j &lt; len(intermediate) &amp;&amp; intermediate[j].Key == intermediate[i].Key {
         j++
      }
      values := []string{}
      for k := i; k &lt; j; k++ {
         values = append(values, intermediate[k].Value)
      }
      fmt.Println(intermediate[i].Key)
      fmt.Println(values)
      output := reducef(intermediate[i].Key, values)

      // this is the correct format for each line of Reduce output.
      fmt.Fprintf(ofile, &quot;%v %v\n&quot;, intermediate[i].Key, output)

      i = j
   }

   ofile.Close()
}

//
// load the application Map and Reduce functions
// from a plugin file, e.g. ../mrapps/wc.so
//
func loadPlugin(filename string) (func(string, string) []mr.KeyValue, func(string, []string) string) {
   p, err := plugin.Open(filename)
   if err != nil {
      log.Fatalf(&quot;cannot load plugin %v&quot;, filename)
   }
   xmapf, err := p.Lookup(&quot;Map&quot;)
   if err != nil {
      log.Fatalf(&quot;cannot find Map in %v&quot;, filename)
   }
   mapf := xmapf.(func(string, string) []mr.KeyValue)
   xreducef, err := p.Lookup(&quot;Reduce&quot;)
   if err != nil {
      log.Fatalf(&quot;cannot find Reduce in %v&quot;, filename)
   }
   reducef := xreducef.(func(string, []string) string)

   return mapf, reducef
}

</code></pre>
<p>mrapp/wc.go的代码如下：</p>
<pre><code class="language-go">
package main

//
// a word-count application &quot;plugin&quot; for MapReduce.
//
// go build -buildmode=plugin wc.go
//

import &quot;6.824/mr&quot;
import &quot;unicode&quot;
import &quot;strings&quot;
import &quot;strconv&quot;

//
// The map function is called once for each file of input. The first
// argument is the name of the input file, and the second is the
// file's complete contents. You should ignore the input file name,
// and look only at the contents argument. The return value is a slice
// of key/value pairs.
//
func Map(filename string, contents string) []mr.KeyValue {
   // function to detect word separators.
   ff := func(r rune) bool { return !unicode.IsLetter(r) }

   // split contents into an array of words.
   words := strings.FieldsFunc(contents, ff)

   kva := []mr.KeyValue{}
   for _, w := range words {
      kv := mr.KeyValue{w, &quot;1&quot;}
      kva = append(kva, kv)
   }
   return kva
}

//
// The reduce function is called once for each key generated by the
// map tasks, with a list of all the values created for that key by
// any map task.
//
func Reduce(key string, values []string) string {
   // return the number of occurrences of this word.
   return strconv.Itoa(len(values))
}

</code></pre>
<p>然后在shell里执行</p>
<pre><code class="language-bash">
$ go build -race -buildmode=plugin ../mrapps/wc.go
$ rm mr-out*
$ go run -race mrcoordinator.go pg-*.txt

</code></pre>
<p>最终可以得到结果<code>mr-out-0</code></p>
<pre><code>A 509
ABOUT 2
ACT 8
ACTRESS 1
ACTUAL 8
ADLER 1
ADVENTURE 12
...

</code></pre>
<h2 id="mr的分布式设计"><a class="header" href="#mr的分布式设计">MR的分布式设计</a></h2>
<p>那么如何设计一个具有水平扩展性的分布式计算框架呢？</p>
<p>在这个计算框架下，使用方只要写map和reduce函数，再指定所要执行的文件，就可以在成百上千的机器上并行的去跑这些执行任务，最终得到总的结果。</p>
<p>在这个框架下，如果有的计算节点没有完成它的map或者reduce任务，这个框架需要重新指定别的计算节点去执行任务。</p>
<p>谷歌给出的方案如下：</p>
<p><img src="./assets/mr_f1.png" alt="mr_f1" /></p>
<p>关于该图的具体解释请参考论文里的内容。（偷个懒hhhh）</p>
<p>分布式理论最初应用在工业界的时候，为了达到最终一致性，为了容错，
人们倾向于有一个master和一群worker，worker出错了的话master会及时感知到，从而触发兜底方案。</p>
<p>而master出错的话，就手动去恢复，相当于把错误限制在为数不多的master机器上。</p>
<p>而mit6.824的lab1中，就是让我们去实现这样一个框架。<br />
时序图如下：</p>
<h3 id="stage1初始化和map阶段"><a class="header" href="#stage1初始化和map阶段">stage1——初始化和map阶段：</a></h3>
<p><img src="./assets/mr_f2.png" alt="mr_f2" /></p>
<h3 id="stage2reduce和完成阶段"><a class="header" href="#stage2reduce和完成阶段">stage2——reduce和完成阶段：</a></h3>
<p><img src="./assets/mr_f3.png" alt="mr_f3" /></p>
<h2 id="问题"><a class="header" href="#问题">问题</a></h2>
<ol>
<li>过了这么多年，目前好用的计算框架除了Mapreduce，还有什么？</li>
<li>Mapreduce不适合处理流式数据，或者数据之间存在关联的时候也不适合，那应该咋办？</li>
</ol>

                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->
                            <a rel="prev" href="chapter_1.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                <i class="fa fa-angle-left"></i>
                            </a>

                            <a rel="next" href="GFS.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                <i class="fa fa-angle-right"></i>
                            </a>

                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">
                    <a rel="prev" href="chapter_1.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                        <i class="fa fa-angle-left"></i>
                    </a>

                    <a rel="next" href="GFS.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                        <i class="fa fa-angle-right"></i>
                    </a>
            </nav>

        </div>




        <script type="text/javascript">
            window.playground_copyable = true;
        </script>


        <script src="elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="mark.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="searcher.js" type="text/javascript" charset="utf-8"></script>

        <script src="clipboard.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="highlight.js" type="text/javascript" charset="utf-8"></script>
        <script src="book.js" type="text/javascript" charset="utf-8"></script>

        <!-- Custom JS scripts -->


    </body>
</html>
